题目
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。
示例 1:
1 2 3
| 输入:intervals = [[1,3],[2,6],[8,10],[15,18]] 输出:[[1,6],[8,10],[15,18]] 解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
|
示例 2:
1 2 3
| 输入:intervals = [[1,4],[4,5]] 输出:[[1,5]] 解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。
|
提示:
- 1 <= intervals.length <= 104
- intervals[i].length == 2
- 0 <= starti <= endi <= 104
注意事项
sort函数在对vector进行排序时,似乎会默认优先排最前面的元素,相同时排下个元素。不需要额外的lambda表达式
这道题需要画出来线段图进行分析,很容易发现sort就可以解题。剩下的就是写法和实现了。
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { int n =intervals.size();
vector<vector<int>> ans; sort(intervals.begin(),intervals.end(),[&](vector<int> interval1,vector<int> interval2){ if(interval1[0]!=interval2[0]){ return interval1[0]<interval2[0]; }else{ return interval1[1]<interval2[1]; } });
for(int i=0;i<n;i++){ if(ans.size()==0 || ans[ans.size()-1][1]<intervals[i][0]){ ans.push_back({intervals[i][0],intervals[i][1]}); }else{ ans[ans.size()-1][1] = max(ans[ans.size()-1][1],intervals[i][1]); } }
return ans; } };
|
原文链接: https://zijian.wang/2021/09/13/56. 合并区间(排序)/
版权声明: 转载请注明出处.